package xyz.naokeziteng.data_structure.graph_theory;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author hawk
 * @date 2022/10/8
 * @desc 图的广度优先遍历
 **/
public class GraphBFS {

    private Graph G;
    private boolean[] visited;
    private List<Integer> levelOrder = new ArrayList<>();


    public GraphBFS(Graph G) {
        this.G = G;
        this.visited = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++) {
            if (!visited[v]) {
                bfs(v);
            }
        }
    }

    //广度优先遍历
    private void bfs(int s) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(s);
        visited[s] = true;
        while (!queue.isEmpty()) {
            int v = queue.poll();
            levelOrder.add(v);
            for (int w : G.adj(v)) {
                if (!visited[w]) {
                    queue.offer(w);
                    visited[w] = true;
                }
            }
        }
    }


    public Iterable<Integer> levelOrder() {
        return levelOrder;
    }


    public static void main(String[] args) {
        GraphBFS bfs = new GraphBFS(new Graph("src/main/resources/g.txt"));
        System.out.println(bfs.levelOrder());
    }
}
